//
// Created by 高森森 on 2022/1/29.
//

#ifndef LEETCODE_SOLUTION14_H
#define LEETCODE_SOLUTION14_H
#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>
using namespace std;

class Solution14 {
public:
     vector<bool>visited;
     vector<int>father;
     int count;
     void dfs(int i, vector<vector<int>>&isConnected){
         if(visited[i]){
             return;
         }
         visited[i]= true;
         for(int j=0;j<isConnected.size();j++){
             if(isConnected[i][j]==1&&!visited[j]){
                 dfs(j,isConnected);
             }
         }

     }
    int findCircleNum(vector<vector<int>>& isConnected) {
         int n=isConnected.size();
         visited.assign(n,false);
         for(int i=0;i<n;i++){
             if(!visited[i]){
                 dfs(i,isConnected);
                 count++;
             }
         }
         return count;
    }
    int findCircleNum2(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        queue<int>que;
        visited.assign(n,false);
        for(int i=0;i<n;i++){
            if(!visited[i]){
               que.push(i);
               while(!que.empty()){
                   int node=que.front();
                   que.pop();
                   visited[node]= true;
                   for(int j=0;j<n;j++){
                       if(isConnected[node][j]==1&&!visited[j]){
                           que.push(j);
                       }
                   }
               }
                count++;
            }
        }
        return count;
    }
    int find(int x){
         if(father[x]==x)
             return x;
         else
             return find(father[x]);
     }
     void merge(int i,int j){
         father[find(i)]=find(j);
     }
    //并查集
    int findCircleNum3(vector<vector<int>>& isConnected) {
            int n=isConnected.size();
            father.reserve(n);
         //初始化
         for(int i=0;i<n;i++){
             father[i]=i;
         }
         for(int i=0;i<n;i++)
             for(int j=i+1;j<n;j++)
             {
                 if(isConnected[i][j]==1)
                     merge(i,j);
             }
         int count=0;
         for(int i=0;i<n;i++)
         {
             if(father[i]==i)
                 count++;
         }
         return count;
     }
};


#endif //LEETCODE_SOLUTION14_H
